package leetcode_classic150;

import model.ListNode;
import model.TreeNode;

import java.util.*;

public class Demo5 {

    // 17. 电话号码的字母组合
    private StringBuilder path;
    private List<String> res;
    private final String[] flag = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        res = new ArrayList<>();
        if (digits.length() == 0) return res;

        path = new StringBuilder();
        dfs(0, digits.toCharArray());
        return res;
    }

    private void dfs(int pos, char[] digits) {
        if (pos == digits.length) {
            res.add(path.toString());
            return;
        }

        int index = digits[pos] - '0';
        for (char ch : flag[index].toCharArray()) {
            path.append(ch);
            dfs(pos + 1, digits);
            path.deleteCharAt(path.length() - 1);
        }
    }



    // 77. 组合
//    private List<Integer> path;
//    private List<List<Integer>> res;
//
//    public List<List<Integer>> combine(int n, int k) {
//        path = new ArrayList<>();
//        res = new ArrayList<>();
//        if (n < k) return res;
//
//        dfs(n, 1, k);
//        return res;
//    }
//
//    private void dfs(int n, int num, int k) {
//        if (path.size() == k || num > n) {
//            if (path.size() == k) res.add(new ArrayList<>(path));
//            return;
//        }
//
//        for (int i = num; i <= n; i++) {
//            path.add(i);
//            dfs(n, i + 1, k);
//            path.remove(path.size() - 1);
//        }
//    }




    // 46. 全排列
//    private boolean[] vis;
//    private List<Integer> path;
//    private List<List<Integer>> res;
//
//    public List<List<Integer>> permute(int[] nums) {
//        path = new ArrayList<>();
//        res = new ArrayList<>();
//        vis = new boolean[nums.length];
//
//        dfs(nums);
//        return res;
//    }
//
//    private void dfs(int[] nums) {
//        if (path.size() == nums.length) {
//            res.add(new ArrayList<>(path));
//            return;
//        }
//
//        for (int i = 0; i < nums.length; i++) {
//            if (!vis[i]) {
//                path.add(nums[i]);
//                vis[i] = true;
//                dfs(nums);
//                path.remove(path.size() - 1);
//                vis[i] = false;
//            }
//        }
//    }



    // 39. 组合总和
//    private List<Integer> path;
//    private List<List<Integer>> res;
//
//    public List<List<Integer>> combinationSum(int[] candidates, int target) {
//        Arrays.sort(candidates);
//        path = new ArrayList<>();
//        res = new ArrayList();
//
//        dfs(0, 0, target, candidates);
//        return res;
//    }
//    private void dfs(int pos, int sum, int target, int[] candidates) {
//        if (sum >= target || pos == candidates.length) {
//            if (sum == target) res.add(new ArrayList<>(path));
//            return;
//        }
//
//        if (sum + candidates[pos] > target) return;
//        // 选
//        path.add(candidates[pos]);
//        dfs(pos, sum + candidates[pos], target, candidates);
//        path.remove(path.size() - 1);
//        // 不选
//        dfs(pos + 1, sum, target, candidates);
//    }




    // 79. 单词搜索
    private int[] dx = new int[]{0,0,1,-1};
    private int[] dy = new int[]{1,-1,0,0};
    private boolean[][] vis;
    private int n, m;

    public boolean exist(char[][] board, String word) {
        n = board.length; m = board[0].length;
        vis = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == word.charAt(0)) {
                    if (dfs(i, j, 0, board, word)) return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int i, int j, int pos, char[][] board, String word) {
        vis[i][j] = true;
        if (pos == word.length() - 1) return true;

        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < n && y >= 0 && y < m && board[x][y] == word.charAt(pos + 1) && !vis[x][y]) {
                if (dfs(x, y, pos + 1, board, word)) return true;
            }
        }

        vis[i][j] = false;
        return false;
    }




    // 52. N 皇后 II
    private boolean[] col;  // 列
    private boolean[] a;    // 正对角线
    private boolean[] b;    // 斜对角线
    private int ret;

    public int totalNQueens(int n) {
        col = new boolean[n];
        a = new boolean[n * 2];
        b = new boolean[n * 2];

        dfs(0, n);
        return ret;
    }
    private void dfs(int i, int n) {
        if (i == n) {
            ret++;
            return;
        }

        for (int j = 0; j < n; j++) {
            if (!col[j] && !a[j - i + n] && !b[i + j]) {
                col[j] = a[j - i + n] = b[i + j] = true;
                dfs(i + 1, n);
                col[j] = a[j - i + n] = b[i + j] = false;
            }
        }
    }



    // 108. 将有序数组转换为二叉搜索树
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildBST(nums, 0, nums.length - 1);
    }
    private TreeNode buildBST(int[] nums, int left, int right) {
        if (left > right) return null;

        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = buildBST(nums, left, mid - 1);
        root.right = buildBST(nums, mid + 1, right);
        return root;
    }



    // 148. 排序链表
    public static ListNode sortList(ListNode head) {
        if (head == null) return null;
        return mergeSort(head, null);
    }

    private static ListNode mergeSort(ListNode head, ListNode tail) {
        if (head == null) return null;
        if (head == tail) {
            head.next = null;
            return head;
        }

        ListNode fast = head.next, slow = head;
        while (fast != tail && fast.next !=  tail) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode l2 = mergeSort(slow.next, tail);
        ListNode l1 = mergeSort(head, slow);

        ListNode newHead = new ListNode();
        ListNode t = newHead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                t.next = l1;
                l1 = l1.next;
            } else {
                t.next = l2;
                l2 = l2.next;
            }
            t = t.next;
        }
        if (l1 == null) t.next = l2;
        if (l2 == null) t.next = l1;
        return newHead.next;
    }




    // 208. 实现 Trie (前缀树)
    class Trie {
        private Trie[] children;
        private boolean isEnd;

        public Trie() {
            children = new Trie[26];
        }

        public void insert(String word) {
            Trie cur = this;
            for (char ch : word.toCharArray()) {
                int index= ch - 'a';
                if (cur.children[index] == null) {
                    cur.children[index] = new Trie();
                }
                cur = cur.children[index];
            }

            cur.isEnd = true;       // 这是一个单词的结束标志
        }

        public boolean search(String word) {
            Trie cur = searchPrefix(word);
            if (cur == null) return false;

            return cur.isEnd;
        }

        public boolean startsWith(String prefix) {
            Trie cur = searchPrefix(prefix);
            if (cur == null) return false;

            for (Trie t : cur.children) {
                if (t != null) return true;
            }
            return cur.isEnd;
        }

        private Trie searchPrefix(String word) {
            Trie cur = this;
            for (char ch : word.toCharArray()) {
                int index= ch - 'a';
                if (cur.children[index] == null) {
                    return null;        // 表示该单词或其前缀不存在
                }
                cur = cur.children[index];
            }
            return cur;
        }
    }




    // 211. 添加与搜索单词 - 数据结构设计
    static class WordDictionary {
        private WordDictionary[] next;
        private boolean isEnd;

        public WordDictionary() {
            next = new WordDictionary[26];
        }

        public void addWord(String word) {
            WordDictionary cur = this;
            for (char ch : word.toCharArray()) {
                int index = ch - 'a';
                if (cur.next[index] == null) cur.next[index] = new WordDictionary();
                cur = cur.next[index];
            }
            cur.isEnd = true;
        }

        public boolean search(String word) {
            WordDictionary cur = this;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                if (ch == '.') {
                    for (int j = 0; j < 26; j++) {
                        if (cur.next[j] != null && dfs(cur.next[j], word, i + 1)) return true;
                    }
                    // 所有情况都列举完，若没有返回 true，则一定不存在该单词
                    return false;
                } else {
                    int index = ch - 'a';
                    if (cur.next[index] == null) return false;
                    cur = cur.next[index];
                }

            }

            return cur.isEnd;
        }

        private boolean dfs(WordDictionary cur, String word, int pos) {
            if (pos == word.length()) return cur.isEnd;

            // 对于非 '.' 字符的处理
            int index = word.charAt(pos) - 'a';
            if (word.charAt(pos) != '.') {
                if (cur.next[index] == null) return false;
                return dfs(cur.next[index], word, pos + 1);
            }

            // 若该位置为非 '.'，则上面一定会返回
            // 对于 '.' 字符的处理
            for (int j = 0; j < 26; j++) {
                if (cur.next[j] != null && dfs(cur.next[j], word, pos + 1)) return true;
            }
            return false;
        }
    }


    //  127. 单词接龙
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>();          // 统计单词本中单词
        set.addAll(wordList);
        if (!set.contains(endWord)) return 0;

        Queue<String> q = new LinkedList<>();       // 作为单词变换过程中的工作队列
        q.offer(beginWord);

        int res = 1;
        Set<String> flag = new HashSet<>();         // 统计哪些单词已经变换过，防止重复变换
        flag.add(beginWord);
        while (!q.isEmpty()) {
            for (int sz = q.size(); sz-- > 0; ) {
                String s = q.poll();

                for (int i = 0; i < s.length(); i++) {
                    char[] arr = s.toCharArray();
                    // 对字符串 s 当前下标尝试进行替换，只要符合出现 set 中，且之前没有变换过，就加入队列中
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        arr[i] = ch;
                        String tmp = new String(arr);

                        if (tmp.equals(endWord)) return res + 1;
                        if (set.contains(tmp) && !flag.contains(tmp)) {
                            q.offer(tmp);
                            flag.add(tmp);
                        }
                    }
                }
            }
            res++;
        }
        return 0;
    }


    // 23. 合并 K 个升序链表
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        return mergeSort(lists, 0, lists.length - 1);
    }
    private ListNode mergeSort(ListNode[] lists, int left, int right) {
        if (left >= right) return lists[left];

        int mid = (left + right) / 2;
        ListNode l1 = mergeSort(lists, left, mid);
        ListNode l2 = mergeSort(lists, mid + 1, right);

        ListNode res = new ListNode();
        ListNode tail = res;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        if (l1 != null) tail.next = l1;
        if (l2 != null) tail.next = l2;
        return res.next;
    }



    // 53. 最大子数组和
    public int maxSubArray(int[] nums) {
        // dp[i]: 以 i 位置为结尾的所有子数组中最大的子数组的和
        int n = nums.length;
        int[] dp = new int[n + 1];

        int res = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            dp[i] = nums[i - 1];
            if (dp[i - 1] > 0) dp[i] += dp[i - 1];
            res = Math.max(res, dp[i]);
        }
        return res;
    }



    // 74. 搜索二维矩阵
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = matrix.length - 1, j = 0;
        while(i >= 0 && j < matrix[0].length) {
            if(matrix[i][j] == target) return true;
            else if(matrix[i][j] > target) i--;
            else j++;
        }
        return false;
    }



    // 909. 蛇梯棋
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);


        int ret = 0;
        boolean[] vis = new boolean[n * n + 1];
        vis[1] = true;
        while (!q.isEmpty()) {
            for (int sz = q.size(); sz > 0; sz--) {
                Integer f = q.poll();

                for (int num = f + 1; num <= Math.min(f + 6, n * n); num++) {
                    if (num == n * n) return ret + 1;

                    int x = n - 1 - (num - 1) / n, y = (num - 1) % n;
                    if (x % 2 == n % 2) y = n - 1 - y;
                    int loca = board[x][y] != -1 ? board[x][y] : num;
                    if (loca == n * n) return ret + 1;
                    if (!vis[loca]) {
                        q.offer(loca);
                        vis[loca] = true;
                    }
                }
            }
            ret++;
        }
        return -1;
    }



    // 172. 阶乘后的零
    public int trailingZeroes(int n) {
        // 这些数中可以分解出的 5 的个数，即为尾随 0 的个数
        int res = 0;
        for (int i = 5; i <= n; i += 5) {
            res += calc(i);
        }
        return res;
    }
    private int calc (int num) {
        int ret = 0;
        while (num > 0 && num % 5 == 0) {
            ret++;
            num /= 5;
        }
        return ret;
    }



    // 50. Pow(x, n)
    public double myPow(double x, int n) {
        double ret = dfs(x, Math.abs(n));
        return n >= 0 ? ret : 1.0 / ret;
    }
    private double dfs(double x, int n) {
        if (n == 0) return 1.0;
        double y = dfs(x, n / 2);
        return n % 2 == 0 ? y * y : y * y * x;
    }




    // 190. 颠倒二进制位
    public int reverseBits(int n) {
        int ret = 0;
        for (int i = 0; i < 16; i++) {
            int left = 31 - i, right = i;
            int leftValue = (n >> left) & 1;
            int rightValue = (n >> right) & 1;

            if (leftValue == 1) ret |= (leftValue<<right);
            if (rightValue == 1) ret |= (rightValue<<left);
        }
        return ret;
    }



    // 918. 环形子数组的最大和
    public int maxSubarraySumCircular(int[] nums) {
        // f[i]: 以 i 位置为结尾的所有子数组中，子数组之和的最大值
        // g[i]: 以 i 位置为结尾的所有子数组中，子数组之和的最小值
        int n = nums.length;
        int[] f = new int[n + 1], g = new int[n + 1];

        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE, sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += nums[i - 1];
            f[i] = Math.max(nums[i - 1], nums[i - 1] + f[i - 1]);
            g[i] = Math.min(nums[i - 1], nums[i - 1] + g[i - 1]);

            max = Math.max(max, f[i]);
            min = Math.min(min, g[i]);
        }

        if (sum == min) return max;
        return Math.max(max, sum - min);
    }



    // 35. 搜索插入位置
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return left;
    }


    // 162. 寻找峰值
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1, mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) left = mid + 1;
            else right = mid;
        }
        return left;
    }



    // 33. 搜索旋转排序数组
    public int search(int[] nums, int target) {
        // 1. 先找到较小区间最左边端点的下标
        int n = nums.length;
        int left = 0, right = n - 1, mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] > nums[n - 1]) left = mid + 1;
            else right = mid;
        }

        // 2. 判断 target 在哪个区间
        if (target > nums[n - 1]) {
            left = 0;
            right--;
        } else right = n - 1;

        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }



    // 34. 在排序数组中查找元素的第一个和最后一个位置
    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[]{-1, -1};
        if (nums.length == 0) return ret;
        int left = 0, right = nums.length - 1, mid;

        // 寻找左端点
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        if (nums[left] != target) return ret;
        ret[0] = left;

        // 寻找右端点
        for (right = nums.length - 1; left < right; ) {
            mid = left + (right - left + 1) / 2;
            if (nums[mid] > target) right = mid - 1;
            else left = mid;
        }
        ret[1] = left;
        return ret;
    }



    // 154. 寻找旋转排序数组中的最小值 II
    public int findMin(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1, mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) left = mid + 1;
            else if (nums[mid] < nums[right]) right = mid;
            else right--;
        }
        return nums[left];
    }


}
